package cm.unit2.theme4;

public class HasPath {

	/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
	public static boolean[][]check = null;
	public static boolean flag = false;
	
    public boolean hasPath (char[][] matrix, String word) {
    	check = new boolean[matrix.length][matrix[0].length];
    
    	for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (matrix[i][j]==word.charAt(0)) {
					// 看有没有路
					findPath(matrix, word,i,j,0);
					if (flag==true) {
						return true;
					}
				}
			}
		}
		return false;
    }
    
    public static void findPath(char[][] matrix, String word,int x,int y,int index) {
		// 找到路径了
    	if (index >= word.length()) {
			flag = true;
			return;
		}
    	
    	// 如果越界
    	if(x<0 || y<0 || x>=matrix.length || y>=matrix[0].length || check[x][y]==true) {
    		return;
    	}
    	
    	// 如果matrix[x][y]==word.charAt(index)
    	if(matrix[x][y]==word.charAt(index)) {
			// 探索下一步
    		check[x][y] = true;
    		findPath(matrix, word, x+1, y, index+1);
    		findPath(matrix, word, x-1, y, index+1);
    		findPath(matrix, word, x, y+1, index+1);
    		findPath(matrix, word, x, y-1, index+1);
    		check[x][y] = false;
		}
    	// 如果matrix[x][y]!=word.charAt(index)
    	else {
			return;
		}
	}
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HasPath hasPath = new HasPath();
		char [][]matrix = {{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
		String word = "abcced";
		System.out.println(hasPath.hasPath(matrix, word));;
	}

}
